

/**
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public abstract class StringTree {

    /**
     * Parent node of this node.
     */
    protected StringTree parent;
    /**
     * Left and right child of the node.
     */
    protected StringTree leftchild;
    protected StringTree rightchild;
    /*
     * Value of the node.
     */
    protected String label;
    /**
     * Constants for path
     */
    protected static final String left = "left";
    protected static final String right = "right";
    protected static final String notFound = "Node not found.";
    /**
     * Constants for toString / toTree
     */
    protected static final String mark = "- ";
    protected static final String ws = "  ";


    protected StringTree(StringTree parent,
            StringTree leftchild, StringTree rightchild, String label) {
        this.parent = parent;
        this.leftchild = leftchild;
        this.rightchild = rightchild;
        this.label = label;
    }

    private StringTree() {        
    }

    /**
     * Checks if the node or subtree contains a node with the value of node.
     * @param node Value of a node to look for.
     * @return Returns true if it is found, else false.
     */
    public boolean contains(String node) {
        boolean found = false;
        if (label.toString().compareTo(node) == 0) {
            return true;
        } else {
            if (leftchild != null) {
                found = leftchild.contains(node);
            }
            if (found == false && rightchild != null) {
                found = rightchild.contains(node);
            }
        }
        return found;
    }

    /**
     * Gets the path to the node we are looking for.
     * First checks if it's itself, if it is, we can return "". Then checks if it is
     * found in the left/right child. If so, it calls the same method there, adding the path taken
     * in front.
     * @param node Value of a node to look for.
     * @return Returns the String "" if its the root node, "left" or "right" for every step.
     */
    public String search(String node) {
         if (label.toString().compareTo(node) == 0) {
            return "";
        } else {
            if (leftchild != null && leftchild.contains(node)) {
                return left + " " + leftchild.search(node).trim();
            } else if (rightchild != null && rightchild.contains(node)) {
                return right + " " + rightchild.search(node).trim();
            } else {
                return notFound;
            }
        }
    }

    /**
     * Adds a node with the value of node. How to add it is defined in subclasses.
     * @param node Value of the node.
     */
    public abstract void add(String node);

    /**
     * Returns a text represantation of the tree.
     */
    @Override
    public String toString() {
        return drawTree(0);
    }

    /**
     * Draws a tree by recursive calling the method on child nodes, increasing value.
     * @param val Depth-Level to add.
     * @return
     */
    private String drawTree(int val) {
        String prepart = "";
        if (val == 0) {
            prepart = "";
        } else {
            for (int i = 1; i < val; i++) {
                prepart += ws;
            }
            prepart += mark;
        }
        String text = prepart + label + "\n";
        if (leftchild != null) {
            text += leftchild.drawTree(val + 1);
        }
        if (rightchild != null) {
            text += rightchild.drawTree(val + 1);
        }
        return text;
    }
}
